SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Query evaluation</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Query evaluation</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Not to be confused with <a href="Question_answering" title="Question answering">question answering</a>.</div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

<p>In <a href="Database_theory" title="Database theory">database theory</a>, the <b>query evaluation</b> problem is the <a href="Computational_problem" title="Computational problem">problem</a> of determining the answers to a query on a database. Research in database theory aims at determining the <a href="Computational_complexity" title="Computational complexity">computational complexity</a> of answering different kinds of queries over databases, in particular over <a href="Relational_database" title="Relational database">relational databases</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Formal_definition">Formal definition</h2></div>

<p>The query evaluation problem takes two inputs: the query to be answered, and the database on which to answer it. The output of the problem is the set of answers to the query on the database. If the queries are <i>Boolean queries</i>, i.e., queries have a yes or no answer (for example, <a href="Boolean_conjunctive_query" title="Boolean conjunctive query">Boolean conjunctive queries</a>) then the query evaluation problem is a <a href="Decision_problem" title="Decision problem">decision problem</a>.

</p><p>The query evaluation problem is usually posed for a specific class of queries and databases. For instance, one example of the query evaluation problem would be the problem of evaluating a <a href="Conjunctive_query" title="Conjunctive query">conjunctive query</a> on a <a href="Relational_database" title="Relational database">relational database</a>.

</p><p>The computational complexity of the problem can be measured in different ways,<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> to account for the fact that the two inputs of the problem are different:

</p>

<ul><li>The <b>combined complexity</b> of the query evaluation problem is its <a href="Computational_complexity" title="Computational complexity">computational complexity</a> when measured as a function of the two inputs, i.e., the query and the database, as usual in computational complexity.</li>

<li>The <b>data complexity</b> is the computational complexity when the query is fixed and when the input is just the database. For instance, we say that query evaluation has <a href="PTIME_(complexity)" class="mw-redirect" title="PTIME (complexity)">polynomial-time</a> data complexity for a class of queries if, for every fixed query <i>Q</i> in that class, given a database <i>D</i>, we can compute the answers to <i>Q</i> on <i>D</i> in polynomial time.</li>

<li>Less commonly, we can study the <b>query complexity</b>, which is the computational complexity when the database is fixed and when the input is just the query. This is also called <b>expression complexity</b>.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Query_classes">Query classes</h2></div>

<p>The complexity of query evaluation can be studied for several query classes, for instance acyclic queries, <a href="Conjunctive_query" title="Conjunctive query">conjunctive queries</a>, <a href="Union_of_conjunctive_queries" class="mw-redirect" title="Union of conjunctive queries">unions of conjunctive queries</a>, Datalog, <a href="Regular_path_query" title="Regular path query">regular path queries</a>, etc., up to logical formalisms like <a href="First-order_logic" title="First-order logic">first-order logic</a> or <a href="Monadic_second-order_logic" title="Monadic second-order logic">monadic second-order logic</a>.

</p><p>For instance, for <a href="Boolean_conjunctive_query" title="Boolean conjunctive query">Boolean conjunctive queries</a>, the complexity of query evaluation is polynomial in data complexity: it even falls in the class <a href="AC0" title="AC0">AC0</a>. By contrast, the query complexity and combined complexity are <a href="NP-complete" class="mw-redirect" title="NP-complete">NP-complete</a><sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> by a reduction from <a href="Graph_coloring" title="Graph coloring">3-colorability</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Boolean_versus_non-Boolean_queries">Boolean versus non-Boolean queries</h2></div>

<p>The complexity of query evaluation can be studied for queries that return answers, or for Boolean queries (yes/no queries). However, we can often reduce to the case of Boolean queries. More specifically, if the number of answers to the query is always polynomial in the database size, and if we can rewrite the query to a Boolean query for each answer, then we can reduce query evaluation for a non-Boolean query to polynomially many Boolean query evaluation problems.

</p>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFVardi1982" class="citation book cs1">Vardi, Moshe Y. (1982-05-05). <a rel="nofollow" class="external text" href="https://dl.acm.org/doi/10.1145/800070.802186">"The complexity of relational query languages (Extended Abstract)"</a>. <i>Proceedings of the fourteenth annual ACM symposium on Theory of computing - STOC '82</i>. New York, NY, USA: Association for Computing Machinery. pp. <span class="nowrap">137–</span>146. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F800070.802186">10.1145/800070.802186</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-89791-070-5</bdi>.</cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite id="CITEREFAbiteboulHullVianu1994" class="citation book cs1">Abiteboul, Serge; Hull, Richard; Vianu, Victor (1994-12-02). <i>Foundations of Databases: The Logical Level</i> (1st ed.). Reading, Mass.: Pearson. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-201-53771-0</bdi>.</cite></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite id="CITEREFGrecoScarcello2014" class="citation book cs1">Greco, Gianluigi; Scarcello, Francesco (2014-06-18). <a rel="nofollow" class="external text" href="https://doi.org/10.1145/2594538.2594559">"Counting solutions to conjunctive queries: Structural and hybrid tractability"</a>. <i>Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems</i>. PODS '14. New York, NY, USA: Association for Computing Machinery. pp. <span class="nowrap">132–</span>143. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2594538.2594559">10.1145/2594538.2594559</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4503-2375-8</bdi>.</cite></span>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-09-27" href="https://en.wikipedia.org/wiki/?title=Query_evaluation&oldid=1248136048">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>